/*
 * @lc app=leetcode.cn id=528 lang=typescript
 *
 * [528] 按权重随机选择
 */

// @lc code=start
class Solution {
  // 线段数组
  sum: number[];
  n: number;
  constructor(w: number[]) {
    //   前缀和，划分区间
    // 比如[1,3]，索引0划分到1，索引1划分到(1,3]区间
    this.sum = [...w];
    for (let i = 1; i < this.sum.length; i++) {
      this.sum[i] += this.sum[i - 1];
    }
    this.n = this.sum[this.sum.length - 1];
  }

  pickIndex(): number {
    // [0,n-1]的随机数
    // 二分查找第一个大于x的索引
    const x = (Math.random() * this.n) >> 0;
    let l = 0;
    let r = this.sum.length - 1;
    while (l < r) {
      let mid = (l + r) >> 1;
      if (this.sum[mid] <= x) l = mid + 1;
      else r = mid;
    }
    return l;
  }
}

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(w)
 * var param_1 = obj.pickIndex()
 */
// @lc code=end
